#
# @lc app=leetcode.cn id=416 lang=python
#
# [416] 分割等和子集
#

# @lc code=start
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        num_sum = sum(nums)
        if num_sum % 2 != 0:
            return False
        
        dp = [0]*(num_sum//2+1)
        for i in range(nums[0], num_sum//2+1):
            dp[i] = nums[0]

        for i in range(1, len(nums)):
            for j in range(num_sum//2, nums[i], -1):
                dp[j] = max(dp[j], nums[i]+dp[j-nums[i]])
        
        if dp[-1] == num_sum//2:
            return True
        else:
            return False
        
# @lc code=end

